Packet classification is a necessary precursor to providing security and Quality of Service (QoS) guarantees in advanced network applications. Packets are pieces of information transmitted over a packet-switched network. In addition to data, a packet contains the destination address that defines where the packet is to be delivered and frequently the source address, which indicates where it originated (this address information is typically contained in a “packet header”). Generally, packet classification relates to filtering packets that are to be processed differently from other packets in a network, and then processing those packets in a proscribed way.
Packet classifiers are used in routers, switches, and similar devices to perform these functions of filtering and processing packets. Packet classifiers receive packets to be routed and compare them to a list maintained by a system administrator. If a match is made, the packet is processed in a prescribed manner.
A common requirement in packet classification is for routers to classify packets based on information in packet headers. A packet header contains several fields that contain a variety of information, such as the source and destination addresses, protocols, flags, and type of service. Packets are classified into equivalence classes called flows, which are defined by rules. For example, a flow might be a set of packets that have source addresses that start with the prefix bits S, protocols that are TCP, and that are to be sent to the server port for web traffic. Each flow can have an additional processing instruction associated with it. Examples of instructions include sending a packet to a specific queue, dropping the packet, or copying the packet.
Packet classification must perform at rates approaching 15 million-packets/sec in 10 gigabit/sec Ethernet networks. For a typical packet classifier in a worst-case scenario, each packet must be compared to each rule before a result can be determined. Given “N” rules, this would result in 15×N million comparisons that must be made per second by the packet classifier. Presently, N typically is on the order of 1000. However, as the demands on the Internet become more complex, N could approach 100,000 in the near future. Such a large number of rules would require 1.5 trillion comparisons per second in a typical packet classifier. Additionally, the comparisons used in packet classification are non-trivial consisting of equality and range checking across a plurality of header fields.